# -*- coding:utf-8

# 5346. 二叉树中的列表 显示英文描述
# 用户通过次数200
# 用户尝试次数417
# 通过次数202
# 提交次数686
# 题目难度Medium
# 给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。
#
# 如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。
#
# 一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:

    def __init__(self):
        self._lis = []

    def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
        current = head
        while current is not None:
            self._lis.append(current.val)
            current = current.next

        def dfsbianliTree(node:TreeNode,targetsLis):
            if node is None:
                return False
            nextTargetLis = [0] #算上从头遍历
            for idx in targetsLis:
                if node.val == self._lis[idx]:
                    nextTargetLis.append(idx+1)
                    if idx+1 >= self._lis.__len__():
                        return True ## 找到了序列串

            leftRes = False
            rightRes = False
            if node.left is not None:
                leftRes = dfsbianliTree(node.left,nextTargetLis)

            if node.right is not None:
                rightRes = dfsbianliTree(node.right,nextTargetLis)

            # if node.right is None and node.left is None:
            #     return False

            return leftRes or rightRes

        return dfsbianliTree(root,[0])

        # return True

print(True or False)















